The group \((\Z, +)\) is cyclic and \(1\) is a generator.
The group \((\R, +)\) is not cyclic.
The subgroup \(\{e, s_1\}\) of \(D_n\) for any \(n\) is cyclic and generated by \(s_1\).
In this module, we continue the study of groups that we started in second-year Abstract Algebra. We will, as then, concentrate on finite groups. Following a short introduction and reminder of the essential concepts from Abstract Algebra, we will begin by revisiting permutation groups and use these to introduce the concept of a conjugate. Next we study what happens when groups act on sets, and follow this with a study of the concepts of normal subgroups and quotient groups. Further exploration of group homomorphisms will bring us to one of the major structural theorems for groups, namely the Isomorphism Theorems, which we will be in a position to prove. Finally, we study the three Sylow theorems, proving the first and considering applications of the second and third.
In the second year Abstract Algebra module we gave the formal definition of a group:
Definition 1.1 (Groups) A group is a pair \((G, *)\), where \(G\) is a non-empty set and \(*\) is a binary operation defined on \(G\) such that:
\(G\) is closed under \(*\), that is \[\forall \, x, y \in G, \; x*y \in G;\]
\(*\) is associative on \(G\), that is \[\forall \, x, y, z \in G, \; x * (y * z) = (x * y) * z;\]
\(G\) has an identity with respect to \(*\), denoted \(e\), that is \[\exists \, e \in G \; \mbox{such that} \; \forall \, x \in G \\ e * x = x * e = x;\]
every \(x \in G\) has an inverse in \(G\), denoted \(x^{-1}\), that is \[\forall \, x \in G \; \exists \, x^{-1} \in G \; \mbox{such that} \\ x * x^{-1} = x^{-1} * x = e.\]
A group with the additional property that \[\forall x, y \in G, x * y = y * x\] is called abelian. You were given lots of examples of structures which satisfy the group axioms. Some of these were infinite and abelian (for example \((\Z, +)\), \((\R, +)\), \((\R \backslash \{0\}, \times)\), and \((\C \backslash \{0\}, \times)\)), some were infinite and non-abelian (for example, \(GL(n, \R)\) under matrix multiplication), some were finite and abelian (for example, \(\Z_n\) and \(\Z^{\times}_m\)), and some were finite and non-abelian (for example, \(D_n\), the group of symmetries of a regular \(n\)-gon).
Initially, we would write groups in the form \((G, *)\) to emphasise the fact that a group is a pair, namely a set of objects and a binary operation defined on that set. In this module we shall, largely, relax that formality and refer to groups simply by the name of the set where there is no ambiguity with regard to the binary operation.
Definition 1.2 (Subgroup) Let \(\gx\) be a group, \(H \subseteq G\) (i.e. \(H\) is a subset of the elements of \(G\)). Then \(H\) is a subgroup of \(G\) if and only if \(\hx\) is a group.
In this module we shall use the notation \(H \leq G\) to denote that \(H\) is a subgroup of \(G\).
To check whether a subset of group elements forms a subgroup we need, in the case of infinite groups, to check that the subset is closed under the group binary operation and that every element of \(H\) has an inverse in \(H\). For finite groups we need only check closure.
Lagrange’s Theorem states that the order of any subgroup must divide the order of the group. The converse is not true for groups in general, but is true for abelian groups.
Recall that for any group element, the set formed by taking all integer powers of that element forms a subgroup. Notationally, if \(\gx\) is a group and \(a \in G\), then the set \(\{ a^n \where n \in \Z \}\) forms a subgroup of \(\gx\) called the cyclic subgroup generated by \(a\) and denoted \(\langle a \rangle\).
Definition 1.3 (Cyclic generator) A group, \(G\), is called cyclic if and only if there exists an element \(a \in G\), called a generator of \(G\), such that \(G = \langle a \rangle\).
Example 1.1
The group \((\Z, +)\) is cyclic and \(1\) is a generator.
The group \((\R, +)\) is not cyclic.
The subgroup \(\{e, s_1\}\) of \(D_n\) for any \(n\) is cyclic and generated by \(s_1\).
Note that if \(\gx\) is a cyclic group with generator \(a\), then the order of \(G\) is the same as the period of \(a\) in \(G\). In addition, note that the order of a cyclic subgroup generated by \(a \in G\) is the same as the period of \(a\) in \(G\). For this reason we shall not refer to the period of an element in a group, but, more naturally, to its order (though they mean the same thing). Recall, also, that if \(\gx\) is a finite group of prime order, then it must be cyclic.
Definition 1.4 (Order of an element) Let \(\gx\) be a group with identity element \(e\) and consider \(a \in G\). If, for all positive integers \(n\), \(a^n \neq e\), then \(a\) has infinite order. Otherwise, the order of \(a\) is the smallest positive integer \(k\) such that \(a^k = e\).
Example 1.2
In \(D_4\), \(r_1\) has order \(4\) since \[r_1 \circ r_1 \circ r_1 \circ r_1 = r_1^{4} = e.\]
In \((\Z, +)\), \(1\) has infinite order.
An important consequence of Lagrange’s theorem is that the order of any element in a group must divide the order of the group.
You were then told that any finite group could be completely described by its operation, or Cayley, table.
\(\begin{array}{ccccc} \begin{array}{c|c} &0\\ \hline 0&0 \end{array} & \hspace{1cm} \begin{array}{c|cc} &0&1\\ \hline 0&0&1\\ 1&1&0 \end{array} & \hspace{1cm} \begin{array}{c|ccc} &0&1&2\\ \hline 0&0&1&2\\ 1&1&2&0\\ 2&2&0&1 \end{array} & \hspace{1cm} \begin{array}{c|cccc} &0&1&2&3\\ \hline 0&0&1&2&3\\ 1&1&2&3&0\\ 2&2&3&0&1\\ 3&3&0&1&2 \end{array} & \hspace{1cm} \begin{array}{c|cccc} &0&1&2&3\\ \hline 0&0&1&2&3\\ 1&1&0&3&2\\ 2&2&3&0&1\\ 3&3&2&1&0 \end{array}\\\\ {\Z}_1&\hspace{1cm} {\Z}_2&\hspace{1cm} {\Z}_3&\hspace{1cm}\Z_4&\hspace{1cm}\Z_2\times\Z_2 \end{array}\)
\(\begin{array}{ccc} \begin{array}{c|ccccc} &0&1&2&3&4\\ \hline 0&0&1&2&3&4\\ 1&1&2&3&4&0\\ 2&2&3&4&0&1\\ 3&3&4&0&1&2\\ 4&4&0&1&2&3 \end{array} & \hspace{1cm} \begin{array}{c|cccccc} &0&1&2&3&4&5\\ \hline 0&0&1&2&3&4&5\\ 1&1&2&3&4&5&0\\ 2&2&3&4&5&0&1\\ 3&3&4&5&0&1&2\\ 4&4&5&0&1&2&3\\ 5&5&0&1&2&3&4 \end{array} & \hspace{1cm} \begin{array}{c|cccccc} &0&1&2&3&4&5\\ \hline 0&0&1&2&3&4&5\\ 1&1&2&0&5&3&4\\ 2&2&0&1&4&5&3\\ 3&3&4&5&0&1&2\\ 4&4&5&3&2&0&1\\ 5&5&3&4&1&2&0 \end{array}\\\\ \Z_5&\hspace{1cm}{\Z}_6&\hspace{1cm}S_3\cong D_3 \end{array}\)
Here we have chosen to use the set \(\{0, 1, \ldots , n-1 \}\) to denote the group elements. This is a natural choice when representing the cyclic group of order \(n\) because the Cayley table corresponds to the operation table for addition modulo \(n\), but for the non-cyclic groups, \(\Z_2 \times \Z_2\) and \(S_3\), no particular meaning should be ascribed to these symbols. Indeed, we may take any of these groups and replace the symbols with \(a, b, c, \ldots\) or Cat, Dog, Goldfish, … to obtain a group which, although formally different to the original group (because the underlying set is different) is ‘essentially the same’. This concept of two structures being ‘essentially the same’ is called isomorphism.
Definition 1.5 (Isomorphism) Let \((G_1, *)\) and \((G_2, \odot)\) be groups. Then \((G_1, *)\) and \((G_2, \odot)\) are isomorphic if and only if there exists a mapping \(\theta : G_1 \rightarrow G_2\) (called an isomorphism) such that
An important skill in pure mathematics is to see through the formalism of statements and definitions and understand what is being said. If you do this then concepts will become natural (maybe even obvious) and you will not need to remember very much. Isomorphism is a case in point. If we want to capture the idea that the elements of the Cayley table of one group can be relabelled so as to obtain the Cayley table of another group (subject to some possible rearrangement of the rows and/or columns), then we need to replace each symbol of the first group with a symbol from the second group. This relabelling is exactly what a bijection achieves (make sure you understand why it needs to be both injective and surjective) and, if the resulting Cayley tables are going to be the same, we require the additional property that
\[\begin{array}{c|ccc} *&&y&\\ \hline &&\vdots&\\ x&\cdots&z&\\ &&& \end{array} \hspace{1cm} \longmapsto \hspace{1cm} \begin{array}{c|ccc} \odot&&\theta(y)&\\ \hline &&\vdots&\\ \theta(x)&\cdots&\theta(z)&\\ &&& \end{array}\]
Or, in other words, \(\theta (x*y) = \theta (x) \odot \theta (y)\). Note that if \(\theta\) is an isomorphism from \(G_1\) to \(G_2\) then \(\theta^{-1}\) is an isomorphism from \(G_2\) to \(G_1\), so we say that \(G_1\) and \(G_2\) are isomorphic and write \(G_1 \cong G_2\). It is important to understand the relationship between cyclic and abelian; if a group is cyclic then it is abelian, but the converse does not necessarily hold. Consider \(\Z^{\times}_{12}\), which has the following operation table:
\[\begin{array}{c|cccc} \otimes_{12}&1&5&7&11\\ \hline 1&1&5&7&11\\ 5&5&1&11&7\\ 7&7&11&1&5\\ 11&11&7&5&1 \end{array}\] Clearly the group is abelian (since the operation involves only the multiplication of integers), but note that all non-identity elements have period 2, so the group cannot be cyclic (since the generator of a cyclic group must have period equal to the order of the group).
If in Definition 1.5, we remove condition a. then the resulting map \(\theta\) is what is called a homomorphism. In particular, homomorphisms preserve the ‘multiplicative structure’ but not necessarily the size. More formally, we have:
Definition 1.6 (Homomorphism) Let \((G_1, *)\) and \((G_2, \odot)\) be groups. Then a map \(\theta : G_1 \rightarrow G_2\) such that \[\forall \, x, y \in G_1, \ \theta (x*y) = \theta (x) \odot \theta (y)\] is called a homomorphism.
An isomorphism is a bijective homomorphism.
Definition 1.7 (Left Coset) Let \(\hx\) be a subgroup of \(\gx\). For a fixed element \(g \in G\), the set \(gH = \{gh \where h \in H\}\) is a left coset of \(H\) in \(\gx\). If \(H = \{h_1, h_2, \ldots, h_m\}\) is finite, then \(gH = \{g \times h_1, g \times h_2, \ldots, g \times h_m\}\).
Left (or right) cosets are an extremely important concept in this module; in fact, much of the material from Chapter 4 onwards is centred around the idea of groups where the elements of the set are themselves cosets (the so-called quotient groups).
In first-year Algebra, and Abstract Algebra last year, we used the concept of integers being congruent, or equivalent, to each other modulo some given integer. Formally we have the following:
Definition 1.8 (Congruence of Integers) Let \(a, b, n\) be integers, \(n > 0\). Then \(a\) is congruent to \(b\) modulo \(n\) if and only if \(n \divides (b-a)\).
Notationally, we write that \(a \equiv b \modu n)\). Recall, also, that if two integers are equivalent to each other modulo \(n\), that is the same as saying that they both leave the same principal remainder on division by \(n\). In Abstract Algebra we took this one step further and defined a residue class as follows:
Definition 1.9 (Residue Class) Let \(a, n\) be integers, \(n\) positive. The residue class \([a]_n\) of \(a\) modulo \(n\) is the set of all integers congruent to \(a\) modulo \(n\). (Or, the equivalence class containing \(a\) under congruence modulo \(n\).). That is, \[[a]_n = \{m \where m \in \Z, m \equiv a \modu n) \} = \{a+kn \where k \in \Z \}.\]
Example 1.3
\[\begin{align*} [5]_6 &= \{5+6k | k \in \Z\} = \{\ldots, -7, -1,5,11,17, \ldots \}\\ [0]_5 &= \{5k | k \in \Z\} = \{ \ldots, -10,-5,0,5,10,\ldots\} \end{align*}\]
We note two things about these residue classes. First, for any integers \(a, b, c\), then \(a\) is in the same class as itself; if \(a\) is in the same class as \(b\) then \(b\) is in the same class as \(a\); if \(a\) is in the same class as \(b\) and \(b\) in the same class as \(c\) then \(a\) is in the same class as \(c\). Second, for any given \(n\), the classes partition the set of integers into disjoint sets where every integer is in exactly one of the residue (or equivalence) classes.
Example 1.4
Consider \([3]_4\) \[ [3]_{4} = \{3+ 4k | k \in \Z \} = \{ \ldots, -9,-5,-1,3,7,11,15,\ldots\} \]
It is clear that \(7\) is contained in its equivalence class. The following are also straightforward
The second property is illustrated below:
\[\begin{align*} [0]_3 &= \{\ldots, -6, -3, 0, 3, 6, 9, \ldots \} \\ [1]_3 &= \{\ldots, -5, -2, 1, 4, 7, 10, \ldots \} \\ [2]_3 &= \{\ldots, -4, -1, 2,5, 8,11 \ldots \} \end{align*}\]
So ‘equivalence modulo’ \(3\) partitions the integers into three disjoint sets — every integer is in one and only one of the 3 sets.
We can formalise these two ideas as follows.
Definition 1.10 (Relation) A relation, \(R\), on a non-empty set \(S\) is a non-empty subset of the Cartesian product \(S \times S\).
Note that, as a consequence of this definition, \(R\) is a set of ordered pairs of elements from \(S\), but rather than specifying a subset \(R\) of \(S \times S\), it is usual to specify a rule for when \((a, b) \in R\), where \(a, b \in S\). We write \(aRb\) rather than \((a, b) \in R\) and read this as \(a\) is related to \(b\) (under the relation \(R\)).
Example 1.5 The following are examples of relations.
Let \(S = \{1, 2, 3, 4, 5, 6, 7\}\) and define a relation on \(S\) such that for all \(a, b \in S, \; aRb \ifif \frac{a-b}{2} \in \Z\).
So \(1R1\) as \((1-1)/2 = 0 \in \Z\); \(2R6\) as \((2-6)/2 = -2 \in \Z\). However, \(3 {R \mkern -11mu/} 4\) since \((3-4)/2 = -1/2 \notin \Z\).
Define the relation \(R = \{ (x, y) \where x \in \Z^+, y \in \Z^+, x \neq y \; \text{and} \; x^y = y^x \}\). What does \(R\) contain?
In fact \(R\) is finite and has only \(2\) elements: \[R = \{(2,4),(4,2)\}.\]
Definition 1.11 (Equivalence Relation) A relation, \(R\), on a non-empty set \(S\) is said to be an equivalence relation if and only if, for all \(a, b, c \in S\),
Definition 1.12 (Partition) A partition of a set, \(S\), is a collection, \(P\), of non-empty subsets of \(S\) such that every element of \(S\) is in exactly one member of \(P\).
Note that each member of \(P\) is, in itself, a set.
Theorem 1.1 Let \(R\) be an equivalence relation defined on a set \(S\) and define \[[a] = \{b \in S \where bRa \}.\] Then, \(\{ [a] \where a \in S \}\) is a partition of \(S\).
Proof.
We need to show that every element of \(S\) belongs to one of these sets and also that any two such sets which have an element in common must in fact be equal.
Let \(a \in S\) be arbitrary. Since \(R\) is an equivalence relation, it is reflexive and so \(aRa\) holds. Therefore, by definition, \(a \in [a]\). Since \(a\) was arbitrarily chosen, we conclude that for all \(a \in S\) \(a \in [a]\).
Now let \(a,b \in S\) and suppose that \([a]\) and \([b]\) have a point \(c\) in common, that is \[ c \in [a] \cap [b].\] Let \(a' \in [a]\) be chosen arbitrarily. Since \(a'\) and \(c'\) are in \([a]\) it follows that \(a' R a\) and \(c Ra\). Since \(R\) is a symmetric relation we deduce that \(a R c\) is true as well. Since \(R\) is transitive, the statements \(a' Ra\) and \(aRc\) now mean that \(a' R c\). Using the fact that \(c \in [b]\) we have \(c Rb\). Applying symmetry again we deduce that \(b Rc\) is true also. Transitivity, from the statements \(a' R c\) and \(c R b\), now implies that \(a' R b\). By definition it follows that \(a' \in [b]\). Since \(a' \in [a]\) was arbitrarily chosen we conclude that \([a] \subseteq [b]\).
Swapping the roles of \([a]\) and \([b]\) above, we see that \([b] \subseteq [a]\) as well. Therefore \([a] = [b]\) as required.
We will often refer to each of the members of a partition as an equivalence class. Note that, as a consequence of the above, residue classes are defined by an equivalence relation on the set of integers and, therefore, partition the set of integers. We now return to the property of isomorphism. It is obvious that any group is isomorphic to itself. Furthermore, if \(\theta\) is an isomorphism from \(G_1\) to \(G_2\) then we have noted that \(\theta^{-1}\) is an isomorphism from \(G_2\) to \(G_1\); so if \(G_1 \cong G_2\) then \(G_2 \cong G_1\). An extension of this argument then leads us to the conclusion that if \(G_1 \cong G_2\) and \(G_2 \cong G_3\), then \(G_1 \cong G_3\). Thus isomorphism is an equivalence relation on the collection of all groups (the collection of all groups is technically not a proper set). Now let us consider left coset formation. You will recall that we used a direct argument in Abstract Algebra to show that left cosets partition the group elements (and, along with two other properties we used this to prove Lagrange’s Theorem). This means, therefore, that left coset formation must be an equivalence relation on the set of group elements and if we can define such an equivalence relation we would have an alternative proof to Lagrange’s Theorem. So, let \(G\) be a finite group and \(H\) be a subgroup of \(G\). Consider \(a, b \in G\). We need to find a relation that describes the property of \(a\) and \(b\) lying in the same left coset of \(H\) as each other, that is, \(a\) is related to \(b\) if and only if both \(a\) and \(b\) are in the same left coset of \(H\) in \(G\). Now, since for any subgroup \(H\) we have that \(e \in H\), it follows that \(a\) and \(b\) are in the same left coset of \(H\) in \(G\) if and only if \(aH=bH\) and, hence, \(ah_1=bh_2\) for some \(h_1, h_2 \in H\). Now,
\[\begin{align*} &ah_1 = bh_2\\ \iff &a= bh_2 h-1^{-1} \\ \iff &b^{-1}a =h_2h_1^{-1} \\ \iff &b^{-1}a \in H \end{align*}\]
The last step follows from the fact that if \(h_1, h_2 \in H\), then since \(H\) is itself a group it is closed under product and inverse and, hence, \(h_2h_1^{-1} \in H\). Then it follows that \(b^{-1}a \in H\) and, hence, we must have that for any two group elements \(x\) and \(y\), they are in the same coset if and only if \(y^{-1}x \in H\), for the given subgroup \(H\). (This is just a relabelling where \(x=a\) and \(y=b\)). So we can now define our relation that results in coset formation as follows: let \(H\) be a subgroup of a finite group \(G\) and let \(x, y \in G\), then \(xRy\) if and only if \(y^{-1}x \in H\). We now need to show that this is indeed an equivalence relation.
Reflexive:
\[x^{-1}x = e \in H \implies xRx \forall x \in G\]
Symmetric:
\[y^{-1}x \in H \iff (y^{-1}x)^{-1} \in H \iff x^{-1}y \in H \iff yRx\]
Transitive:
Suppose \(xRy\) and \(yRx\), then \(y^{-1}x \in H\) and \(z^{-1}y \in H\). This means that \((z^{-1}y)(y^{-1}x) \in H\). Therefore \(z^{-1}x \in H\) and \(xRz\).
We have established that left coset formation is an equivalence relation, so we now know that it must partition the group. We also know, from Abstract Algebra, that the size of every coset is equal to the size of \(H\) and, therefore, we can conclude that the size of \(H\) must divide the size of \(G\).
The above also gives us a checking lemma to determine whether two left cosets are equal. It uses the fact that two left cosets are either disjoint or identical and that \(g \in gH\).
Lemma 1.1 Let \(H\) be a subgroup of \(G\) and \(g_1, g_2 \in G\). Then \[g_1H = g_2H \ifif g_1^{-1}g_2 \in H.\]
Proof.
Suppose \(g_1H = g_2H\). Note that \(g_2 \in g_2 H\) since \(g_2 = g_2 e\) and \(e \in H\). Since \(g_1H = g_2 H\) there is an element \(h \in H\) such that \(g_1h = g_2\). Therefore \(h = g_1^{-1}g_2\) and so \(g_1^{-1}g_2 \in H\) as required.
On the other hand, suppose \(g_1^{-1}g_2 \in H\). Let \(h \in H\), then \[g_1h = eh= (g_2g_2^{-1})g_1h = g_2(g_2^{-1}g_{1})h = g_2((g_2^{-1}g_1)h) \in g_2 H\] since \(g_2^{-1}g_1 = (g_1^{-1}g_2)^{-1} \in H\). Similarly, \[g_2h = g_1(g_1^{-1}g_2)h \in g_1 H.\]
Since \(h \in H\) was chosen arbitrarily, we conclude that \(g_1H = g_2H\).
Earlier we presented the Cayley tables of all the isomorphically distinct groups up to order 6, by which we mean that any group of order less than or equal to 6 is isomorphic to exactly one group in that list. The fundamental problem of Group Theory is to produce such a catalogue for all groups, or perhaps just all finite groups. Clearly it is not possible, nor particularly helpful, to produce an infinite list of Cayley tables, but for a given order \(n\) can we describe or generate all of the isomorphically distinct groups of that order? We know this is possible for all of the finite abelian groups, by way of the Fundamental Theorem of Finite Abelian Groups, so, it is the non-abelian groups that cause all the trouble in terms of trying to establish a classification. The most celebrated result in Group Theory is the classification of all finite simple groups. Simple groups will be defined later, but are the building blocks of all finite groups in much the same way that the primes are the building blocks of the positive integers. This classification theorem is the result of over 100 years’ work by thousands of group theorists and it is estimated that its complete proof (if ever assembled in one place) would require about 20,000 pages! In this module we will prove some classification and structure theorems, but we will also look at how groups arise naturally (albeit in some unexpected places). In doing so we shall be looking at the forms that different groups can take - in particular their actions, presentations and representations. The first unexpected place that group theory arises is in the bedroom….
Good mattresses are expensive. Being a frugal individual I wish to maximise the amount of use that I get from my mattress so it is necessary to turn the mattress at regular intervals (say once a month) so as to promote uniform wear. Obviously any turning of the mattress must result in the mattress fitting back onto the bed as intended and, therefore, we can consider this problem in terms of the symmetries of a rectangle (assuming that the mattress is not square!) where the mattress represents the rectangle and the base of the bed represents the two-dimensional plane. Now, we know that the symmetry group of a rectangle is isomorphic to \(\Z_2 \times \Z_2\) (there are only two groups, up to isomorphism, of order 4 and the other is cyclic) and hence there are four positions for the mattress, or one per month for a four-month period. The symmetries are a rotation of \(180^{\circ}\) degrees, a ‘flip’ about the short axis, and a ‘flip’ about the long axis. Suppose we designate as \(A\) the \(180^{\circ}\) rotation (where the mattress remains face up), as \(B\) the ‘flip’ in the long axis of symmetry, and as \(C\) the ‘flip’ in the short axis of symmetry. What is the best sequence of moves for the mattress?
We could try each move in turn:
This is not a good solution since the initial configuration of the mattress is repeated at the end — a configuration is missing,
A better solution, which does not use \(C\), but gives even cover is: \(ABABABA\ldots\)
In the Abstract Algebra module we found that the set of integer powers of an element of a group, \(G\), generates a cyclic subgroup of \(G\). If \(a\) is an element of \(G\), and has finite period \(k\) in \(G\), then this subgroup is \[\langle a \rangle = \{e, a, a^2, \ldots, a^{k-1}\}.\] Since this subgroup has order \(k\), the element \(a\) has order \(k\) (some authors write \(|a| = k\)). If there is an element \(a \in G\) such that \(\langle a \rangle = G\), then, as we know, \(G\) is a cyclic group and \(a\) is a generator of \(G\). Clearly \(\langle a \rangle\) is the smallest subgroup of \(G\) containing \(a\) in the sense that every subgroup of \(G\) which contains \(a\) must also contain \(\langle a \rangle\). We can generalise this to any subset of elements of \(G\).
We can generalise this to the following:
Definition 1.13 Let \(G\) be a group and let \(S = \{a_1, a_2, \ldots \}\) be a subset of the elements of \(G\). The subgroup generated by \(S\) is the smallest subgroup of \(G\) containing \(S\) (we denote this \(\langle S \rangle = \langle a_1, a_2, \ldots \rangle\). If this subgroup is all of \(G\) then \(S\) generates \(G\) and the \(a_i\) are generators of \(G\). If there is a finite set, \(S\), which generates \(G\), then \(G\) is finitely generated.
So, given a group \(G\) and a subset of elements \(S\), what does the subgroup generated by \(S\) look like? The following theorem answers this question.
Theorem 1.2 If \(G\) is a group and \(S = \{a_1, a_2, \ldots \}\) a subset of the elements of \(G\), then the subgroup \(\langle S \rangle\) of \(G\) consists of those elements of \(G\) that are finite products of integral powers of the \(a_i\) (where powers of a given \(a_i\) may occur several times in the product).
Proof.
First observe that a finite product of integral powers of elements of \(S\) must be contained in \(\langle S \rangle\) since \(S\) is contained in \(\langle S \rangle\). It therefore suffices to show that the set \(H\) of finite produces integral powers of elements of \(S\) is a subgroup of \(G\). This is because the set \(H\) would then be a subgroup of \(G\) containing \(S\) that is a subset of \(\langle S \rangle\), as \(\langle S \rangle\) is the smallest subgroup of \(G\) containing \(S\) it must therefore be equal to \(H\).
We check the subgroup criteria hold for \(H\).
Example 1.6
Consider \(D_4\). Note that \(D_4\) is not a cyclic group since it cannot be generated by a single element (the order of \(D_4\) is \(8\) and the order of an element of \(D_4\) is either \(2\) or \(4\)). However \(D_4\) can be generated using a proper subset of elements of \(D_4\).
\[\begin{array}{c|cccccccc} \circ&e&r_1&r_2&r_3&s_1&s_2&s_3&s_4\\ \hline e&e&r_1&r_2&r_3&s_1&s_2&s_3&s_4\\ r_1&r_1&r_2&r_3&e&s_4&s_1&s_2&s_3\\ r_2&r_2&r_3&e&r_1&s_3&s_4&s_1&s_2\\ r_3&r_3&e&r_1&r_2&s_2&s_3&s_4&s_1 \\ s_1&s_1&s_2&s_3&s_4&e&r_1&r_2&r_3 \\ s_2&s_2&s_3&s_4&s_1&r_3&e&r_1&r_2 \\ s_3&s_3&s_4&s_1&s_2&r_2&r_3&e&r_1 \\ s_4&s_4&s_1&s_2&s_3&r_1&r_2&r_3&e \end{array}\]
Let \(S = \{r_1,s_2\}\). Now the set of integral powers of \(r_1\) is precisely \(\{e,r_1, r_2, r_3\}\). To obtain the reflections \(s_1, s_3\) and \(s_4\) observe that
\[\begin{align*} r_1 s_2 &= s_1 \\ r_1 s_1 &= s_4 \\ r_1 s_4 &= s_3 \end{align*}\]
We conclude that \(\gen{r_1, s_2} = D_4\) and \(D_4\) is finitely generated.
In essence, a group presentation is a notation that describes a group in terms of its generators and relations that hold between them. We begin with a definition.
Definition 1.14 (Presentation) A group can be described concisely by the notation \[\langle a, b \ldots \; | \; \text{list of relations between a, b, $\ldots$ , and their powers}\, \rangle,\] where the first part is a list of generators for the group and the second is a list of the relations that generate all the relations that hold between the generators. This notation is called a presentation of the group.
Example 1.7 Consider the presentation \[\langle a, b \; | \; a^2 = b^2 = 1, ab = ba \rangle.\]
The generators both have order \(2\) and commute. This means that any finite product integral powers of the generators \(a,b\) can be reduced, using the relations, to the form \(a^{i}b^{j}\) where \(i,j \in \{0,1\}\). Computing the operation table:
\[ \begin{array}{c|cccc} \ast & 1 & a & b & ab \\ \hline 1 & 1 & a & b & ab \\ a & a & 1 & ab & b \\ b & b & ab & 1 & a \\ ab & ab & b & a & 1 \end{array} \]
Observe that the group is abelian and is in fact isomorphic to \(\Z_2 \times \Z_2\).
Example 1.8 Consider the presentation \[\langle a, b \; | \; a^3 = b^2 = 1, ab = ba^{-1} \rangle.\]
The generator \(a\) has order \(3\) and so has inverse \(a^2\); the generator \(b\) has order \(2\) and is its own inverse. The relation \(ab=ba^{-1}\) means we can move \(b\) to the left of \(a\) at the cost of replacing \(a\) with its inverse. Consequently, by repeatedly moving \(b\)’s to the left of \(a\)’s any finite product of integral powers of \(a\) and \(b\) can be written in the from \(b^{i}a^{j}\) where \(i \in \{0,1\}\) and \(j \in \{0,1,2\}\).
We can compute the operation table. \[ \begin{array}{c|cccccc} \ast & 1 & a & a^2 & b & ba & ba^2 \\ \hline 1 & 1 & a & a^2 & b & ba & ba^2 \\ a & a & a^2 & 1 & ba^2 & b & ba \\ b & b & ba & ba^2 & 1 & a & a^2 \\ ba & ba & ba^2 & a^2 & 1 & a & b \\ ba^2 & ba^2 & b & ba & a & a^2 & 1 \end{array} \] Clearly this group is not abelian since \(ba \ne ab = ba^{2}\).
Looking at the above two presentations, we can see that the first is clearly abelian (because there are only two generators \(a\) and \(b\) and \(ab = ba\)), whereas the second is clearly non-abelian (because \(ab = ba^{-1}\) and \(a^{-1} \neq a\)). In each case it was also easy to determine the order of each group and write out the group elements in some form. In the next two examples this is not so obvious.
Example 1.9 \(\langle a, b \; | \; a^2 = b^2 = 1, (ab)^3 = 1 \rangle.\)
Notice that \(a\) and \(b\) both have order \(2\) in this case. Further observe that since \(ab ab ab = 1\) then \(bab = aba\). Thus \(baba = bbab=ab\) and \(abab= babb = ba\). Any finite product of integral powers of \(a\) and \(b\) can be written as a product of \(a\) and \(b\)’s. Moreover, such a product cannot have consecutive \(a\)’s or consecutive \(b\)’s. Using the observation \(baba =ab\) and \(abab = ba\) we notice that such a product cannot exceed length \(3\). This leaves products of the form \(a, ab,aba, b, ba\). The multiplication table is now
\[
\begin{array}{c|cccccc}
\ast & 1 & a & b & ab & ba & aba \\
\hline
1 & 1 & a & b & ab & ba & aba \\
a & a & 1 & ab & b & ab & ba \\
b & b & ba & 1 & aba & a & ab \\
ba & ba & b & aba & 1 & ab & a \\
aba & aba & ab & ba & a & b & 1
\end{array}
\] Note that is group is isomorphic to \(D_3\). The reflections are \(a,b\) and \(aba\) and the rotations are powers of \(ab\).
Example 1.10 \(\langle a, b \; | \; b^2a = b, ba^2b = a \rangle.\)
This group is the trivial group. From \(b^2 a = b\) we find that \(ba =1\). From \(ba^2b =a\) we find that \(ab = a\) and so \(b =a\). Using \(ba=1\) we see that \(a=1\) as well.
A good presentation provides an efficient description of a group. For example, the dihedral group of order \(2n\), which is isomorphic to the symmetry group of a regular \(n\)-sided polygon, can be defined by the presentation \[D_n = \langle a, b \; | \; a^n = b^2 = 1, ba = a^{-1}b \rangle.\] It is easy to see that any product must belong to the set \(\{1, a, a^2, \ldots, a^{n-1}, b, ab, a^2b, \ldots, a^{n-1}b\}\) and any product may be reduced to an element of this set by reducing powers of \(a\) modulo \(n\), powers of \(b\) modulo 2, and bringing the \(a\)’s to the left, replacing \(a\) with \(a^{-1}\) when it `hops over’ a \(b\).
Example 1.11
For \(D_6\) we have \[\gen{a,b \mid a^6=b^2=1, ba = a^{-1}b}.\]
Given a product, for instance \(a^{11}b^3 a^2b^{-1}a^{-1}b^4a\), we can apply the relation to reduce it to the form \(a^{i}b^{j}\) for \(0 \le i \le 5\) and \(0 \le j < 2\).
\[\begin{align*} a^{11}b^3 a^2b^{-1}a^{-1}b^4a &= a^5 b a^2 b\\ &= a^5 a^{-2}b^2 \\ &= a^3 \end{align*}\]
Informally the free group on a (possibly infinite) set of generators \(\{a, b, c, \ldots\}\) consists of all finite products involving integer powers of the generators where there are no relations to tell us how to reduce products, with the obvious exception that, for example, \(ab^2b^{-3}a=ab^{-1}a\) etc. The products formed in this way are called words. Fundamentally, all groups can be thought of as consisting of infinitely many words but, using relations, we may be able to reduce each of these to a member of a (possibly finite) set. As we have seen, things are not always this easy. For a given presentation it can be difficult to determine the order of the group or even whether it is finite or infinite. This is summed up by the so called Word Problem for groups. The Word Problem is to find an algorithm which will determine whether two words represent the same element. We have such an algorithm for the dihedral group \(D_n\) because we have a way of reducing any given word to one of the \(2n\) elements of \(\{1, a, a^2, \ldots, a^{n-1}, b, ab, a^2b,\ldots, a^{n-1}b\}\). Hence two words are equal if and only if they reduce to the same element. It is hard to imagine that this would not be the case for any group presentation, but remarkably the Word Problem is known to be unsolvable in general.
This is a revision sheet and covers material from Abstract Algebra.
Define \(*\) on \(\rwz\) by \(a*b=|a| \, b\) (so, for example \(2*3=6, -2*3=6, 2*(-3)=-6\) etc.).
If \(H\) is a subgroup of a finite group \(G\) then the right coset of \(H\) by \(g\) is denoted and defined by \[Hg=\{hg \, | \, h\in H\}.\] Prove Lagrange’s Theorem using right cosets (the proof using left cosets was given in the second year Abstract Algebra module). In other words, show that every right coset, \(Hg\), of \(H\) is the same size as \(H\), that two right cosets of \(H\) are either disjoint or equal, and that every element of \(G\) is in a right coset of \(H\). Finally deduce that the order of \(H\) divides the order of \(G\).
Let \(G\) be a group and \(H\) the subset of \(G\) consisting of the identity \(e\) and all elements of \(G\) of order 2, so \(H=\{h\in G| h^2=e\}\). Show that:
In each of the following cases, find the order of the given element in the direct product:
For the example class in Week 3; covers Chapter 1 material. At minimum you should attempt questions 1.4, 1.5 and 1.7.
Let \(R\) be a relation on a non-empty set, \(S\)
In the group \[\langle A, B, C\, |\, A^7=B^3=C^2=1, BA=A^3B, CA=AC, CB=B^2C\rangle\] express each of the following in the form \(A^rB^sC^t\):
In the dihedral group \(D_5=\langle a, b\, | \, a^5=1, b^2=1, ab=ba^{-1} \rangle\), simplify: